HW#1 --- last modified February 28 2019 23:10:08..

Solution set.

Due date: Feb 7

Files to be submitted:
  Hw1.zip
  Hw1.pdf
  Hw1.jff

Purpose: (1) To get a baseline for your understanding before taking this class. (2) To learn the set notations and proof techniques useful for this class. (3) To begin learning about DFAs and NFAs. (4) To experiment with the JFLAP software.

Related Course Outcomes:

Course Outcome #2 -- Construct deterministic and non-deterministic machines for various languages.

Specification:

As was discussed in class, this semester we are testing the efficacy of the JFLAP software. On the first day of class, an informed consent form was passed out and returned by those of you who wished to participate. To minimize the additional burden placed on those who choose to participate versus those that don't, part of this first homework will be to answer questions 7-21 from the JFLAP survey. You should put your answers into a subfolder with your name of the file Hw1.zip. Each member of a group needs to have a subfolder where they have done this. If all the subfolders are present and have date timestamps before Jan. 31, I will give your group 2pts for having completed the task. I will not grade your answers, as these questions cover material that has not yet been convered in class. To create a subfolder each group member as they are doing the problem 7-21 on each page, should click save after having filled out the form either do a screen grab and save the resulting image to prove you filled out the form. Convert these images to a compressed format like jpg, gif, or png and put them in the appropriate subfolder. For people who decide to participate in the study, you can fill our the rest of the survey and submit it. For people who don't want to participate, you do not have to do any of the rest of the survey or submit the survey. You can opt out of the study at any time by simply not submitting one of the surveys during the semester. I will not know who is and who is not participating.

The remainder is of the first assignment is to do the following problems, submit the first three in Hw1.pdf and submit the last one as Hw1.jff:

1. (a) Prove by induction that the number of nodes in a complete 3-ary tree (each nonleaf node has exactly 3 children) of height n is (3ⁿ⁺¹-1)/2. (b) Prove by induction that there is no one to one function from a set of size n+1 into a set of size n. (This is known as the pigeonhole principle).

2. Prove carefully that the relationship on functions from the positive integers to the positive integers f(n)=Θ(g(n)) is an equivalence relation.

3. When installing software on a computer, one frequently encounters an installation wizard that allows the user to configure the software as it is installed. In designing such a wizard, it is sometimes useful to model the various paths through the wizard as a finite automaton. The alphabet are the allowed buttons to be pressed and items one can select. The states are possible wizard windows that could be displayed. One switched between states by reading a symbol from the alphabet, that is presses a button or selects an option. Clicking a button like "Finish" or "Cancel Installation" sends one into an accept state. One property we would like a wizard to have is liveness, that is the user should not be able to get into a nonaccepting state from which there is no path to an accepting state. Pick your favourite installation wizard. Note it in your homework solution. Then draw a model it as a finite automata. Argue whether it does or does not satisfy the liveness condition.

4. Use JFLAP to make a DFA for the language over {a,b} consisting of strings with an even number of b's.

Point Breakdown